package codeTopPractice;


import java.util.ArrayList;
import java.util.List;

/**
 * 给你二叉树的根节点 root，返回其节点值的 层序遍历。（即逐层地，从左到右访问所有节点）。
 */
public class 二叉树的层序遍历 {
    List<List<Integer>> res = new ArrayList<>();

    public static void main(String[] args) {

    }

    public  List<List<Integer>> levelOrder(TreeNode root){

        if(root == null){
            return res;
        }
        helper(root,0);
        return res;

    }

    //递归实现层序遍历，采用一个level值代表树的第level层，每一层对应一个arrayList，该层有值就会被添加到对应的层的arrayList中
    public void helper(TreeNode node,int level){
        //假设root处在第0层，往下层数一次+1
        //判断res的大小，即判断有无创建对应层的ArrayList，没有则新建一个，有则跳过
        if(res.size() == level) res.add(new ArrayList<>());
        //取到对应层的ArrayList并添加值
        res.get(level).add(node.val);

        //若左节点不为空，递归调用helper，层数+1
        if(node.left!=null) helper(node.left,level+1);
        //若右节点不为空，递归调用helper，层数+1
        if(node.right!=null)helper(node.right,level+1);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
